class PriorityQueue {
  constructor() {
    this.nodes = [];
  }

  enqueue(priority, key) {
    this.nodes.push({ key, priority });
    this.sort();
  }

  dequeue() {
    return this.nodes.shift();
  }

  sort() {
    this.nodes.sort((a, b) => a.priority - b.priority);
  }

  isEmpty() {
    return !this.nodes.length;
  }
}

/**
 * @param {number} n
 * @param {number[][]} edges
 * @param {number[]} disappear
 * @return {number[]}
 */
var minimumTime = function (n, edges, disappear) {
  if (n === 1) { return [0] }
  let answer = [0]
  let sideHash = {}
  let pq = new MinPriorityQueue()

  edges.forEach(edge => {
    let [ui, vi, lengthi] = edge
    if (!sideHash[ui]) {
      sideHash[ui] = { [vi]: lengthi }
    } else {
      if (sideHash[ui][vi]) {
        sideHash[ui][vi] = lengthi < sideHash[ui][vi] ? lengthi : sideHash[ui][vi]
      } else {
        sideHash[ui][vi] = lengthi
      }
    }

    if (!sideHash[vi]) {
      sideHash[vi] = { [ui]: lengthi }
    } else {
      if (sideHash[vi][ui]) {
        sideHash[vi][ui] = lengthi < sideHash[vi][ui] ? lengthi : sideHash[vi][ui]
      } else {
        sideHash[vi][ui] = lengthi
      }
    }
  })

  for (let i = 1; i < n; i++) {
    let time = 0
    answer[i] = Infinity
    pq.enqueue(i, Infinity)
    let hash0 = sideHash[0] || {}
  }

  pq.enqueue(0, 0)
  while (!pq.isEmpty()) {
    let { element: currentVertex, priority: currentDistance } = pq.dequeue();
    if (currentDistance > answer[currentVertex]) continue;

    for (let neighbor in sideHash[currentVertex]) {
      let alt = answer[currentVertex] + sideHash[currentVertex][neighbor]
      if (disappear[neighbor] <= alt) { continue; }
      if (alt < answer[neighbor]) {
        answer[neighbor] = alt
        pq.enqueue(neighbor, alt)
      }
    }
  }
  return answer.map((value, i) => value !== Infinity ? value : -1)
};


function dijkstra(graph, start) {
  let distances = {};
  let prev = {};
  let pq = new PriorityQueue();

  // 初始化所有顶点的距离和前驱
  for (let vertex in graph) {
    distances[vertex] = Infinity;
    prev[vertex] = null;
    pq.enqueue(Infinity, vertex);
  }

  distances[start] = 0;
  pq.enqueue(0, start);

  while (!pq.isEmpty()) {
    let { key: currentVertex, priority: currentDistance } = pq.dequeue();

    if (currentDistance > distances[currentVertex]) continue;

    for (let neighbor in graph[currentVertex]) {
      let alt = distances[currentVertex] + graph[currentVertex][neighbor];

      if (alt < distances[neighbor]) {
        distances[neighbor] = alt;
        prev[neighbor] = currentVertex;
        pq.enqueue(alt, neighbor);
      }
    }
  }

  return { distances, prev };
}

// 使用示例
let graph = {
  A: { B: 1, C: 4 },
  F: { E: 6, D: 8 },
  B: { A: 1, C: 2, D: 5 },
  C: { A: 4, B: 2, D: 1 },
  D: { B: 5, C: 1, E: 3 },
  E: { D: 3, F: 6 },
};

let result = dijkstra(graph, 'A');
console.log(result.distances);  // { A: 0, B: 1, C: 3, D: 4, E: 7, F: 13 }
console.log(result.prev);       // { A: null, B: 'A', C: 'B', D: 'C', E: 'D', F: 'E' }


// 给你一个二维数组 edges 表示一个 n 个点的无向图，其中 edges[i] = [ui, vi, lengthi] 表示节点 ui 和节点 vi 之间有一条需要 lengthi 单位时间通过的无向边。

// 同时给你一个数组 disappear ，其中 disappear[i] 表示节点 i 从图中消失的时间点，在那一刻及以后，你无法再访问这个节点。

// 注意，图有可能一开始是不连通的，两个节点之间也可能有多条边。

// 请你返回数组 answer ，answer[i] 表示从节点 0 到节点 i 需要的 最少 单位时间。如果从节点 0 出发 无法 到达节点 i ，那么 answer[i] 为 -1 。